package mashibing.class7;

import java.util.*;

/**
 * 最大线段重合问题（用堆的实现）
 * <p>
 * 给定很多线段，每个线段都有两个数[start, end]，
 * 表示线段开始位置和结束位置，左右都是闭区间
 * 规定：
 * 1）线段的开始和结束位置一定都是整数值
 * 2）线段重合区域的长度必须>=1
 * 返回线段最多重合区域中，包含了几条线段
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-03-29
 */
public class Class7_1_CoverMax {

    public static class Line {
        public int left;
        public int right;

        public Line(int left, int right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "Line{" +
                    "left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public static class LineComparator implements Comparator<Line> {
        @Override
        public int compare(Line o1, Line o2) {
            return o1.left - o2.left;
        }
    }

    public static int coverMax(int[][] arr) {
        if (arr.length <= 1) {
            return arr.length;
        }
        List<Line> lines = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            Line line = new Line(arr[i][0], arr[i][1]);
            lines.add(line);
        }
        // 根据左线段进行排序
        lines.sort(new LineComparator());
        System.out.println(lines);
        // 小根堆存放右线段
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int ans = 0;
        for (Line line : lines) {
            heap.add(line.right);
            while (!heap.isEmpty() && heap.peek() <= line.left){
                heap.poll();
            }
            ans = Math.max(ans,heap.size());
        }
        return ans;
    }

    public static int[][] generateLine(int maxSize, int L, int R) {
        int row = (int) (Math.random() * maxSize);
        int[][] line = new int[row][2];
        for (int i = 0; i < row; i++) {
            int a = (int) (Math.random() * (L + 1));
            int b = (int) (Math.random() * (R + 1));
            if (a == b) {
                b++;
            }
            line[i][0] = Math.min(a, b);
            line[i][1] = Math.max(a, b);
        }
        return line;
    }

    public static void main(String[] args) {
        int[][] ints = generateLine(20, 50, 50);
        int count = coverMax(ints);
        System.out.println(count);
    }
}
